This invention relates generally to a method and apparatus for sending and responding to signaling messages. Specifically, the invention provides controls for a communications network in order to create paths for timely forwarding and delivery of data. Consequently, the end-to-end performance parameters, such as, loss, delay and jitter, have either deterministic or probabilistic guarantees.
The proliferation of high-speed communications links, fast processors, and affordable, multimedia-ready personal computers brings about the need for wide area networks that can carry real time data, like telephony and video. However, the end-to-end transport requirements of real-time multimedia applications present a major challenge that cannot be solved satisfactorily by current networking technologies. Such applications as video teleconferencing, and audio and video multicasting generate data at a wide range of bit rates and require predictable, stable performance and strict limits on loss rates, average delay, and delay variations (xe2x80x9cjitterxe2x80x9d). These characteristics and performance requirements are incompatible with the services that current circuit and packet switching networks can offer.
Circuit-switching networks, which are still the main carrier for real-time traffic, are designed for telephony service and cannot be easily enhanced to support multiple services or carry multimedia traffic. Its synchronous byte switching enables circuit-switching networks to transport data stream at constant rate with little delay or jitter. However, since circuit-switching networks allocate resources exclusively for individual connections, they suffer from low utilization under bursty traffic. Moreover, it is difficult to allocate dynamically circuits of widely different capacities, which makes it a challenge to support multimedia traffic. Finally, the synchronous byte switching of SONET, which embodies the Synchronous Digital Hierarchy (SDH), requires increasingly more precise clock synchronization as the lines speed increases. For further discussion of circuit switching see, for example, [R. Ballart and Y-C. Ching SONET: now it""s the standard optical network, IEEE Communications Magazine, Vol. 29 No. 3, March 1989, pages 8-15.
Packet switching networks like IP-based Internet and Intranets [A. Tannebaum Computer Networks (3rd Ed) Prentice Hall 1996] and ATM [R. Handel, M. N. Huber, and S. Schroder. ATM Networks: Concepts, Protocols, and Applications (2nd Ed.) Addison-Wesley, 1994] handle bursty data more efficiently than circuit switching, due to their statistical multiplexing of the packet streams. However, current packet switches and routers operate asynchronously and provide best effort service only, in which end-to-end delay and jitter are neither guaranteed nor bounded. Furthermore, statistical variations of traffic intensity often lead to congestion that results in excessive delays and loss of packets, thereby significantly reducing the fidelity of real-time streams at their points of reception. In fact, under best effort service, the performance characteristics of a given connection are not even predictable at the time of connection establishment.
Efforts to define advanced services for both IP and ATM have been conducted in two levels: (1) definition of service, and (2) specification of methods for providing different services to different packet streams. The former defines interfaces, data formats, and performance objectives. The latter specifies procedures for processing packets by end-stations and switches/routers. The types of services that were defined for ATM include constant bit rate (CBR), variable bit rate (VBR) and available bit rate (ABR). For IP the defined services include guaranteed performance (bit rate, delay), controlled flow, and best effort (see [J. Wroclawski. Specification of the Controlled-Load Network Element Service. IETF RFC 2211, September 1997] and [S. Shenker et. al. Specification of Guaranteed Quality of Service. IETF RFC 2212. September 1997].
Signaling is a collecting name for methods for specifying desired characteristics of a communication path, establishing such paths for transferring data, and releasing communications paths at the end of the communications session. Signaling has been initially developed for circuit switching networks, which offer a single type of connection, namely, voice-grade circuit. Telephony signaling is carried in-bandxe2x80x94on the same lines that carry the voice signalsxe2x80x94and it aims at reserving resources along the desired path for the exclusive use of the participants of the phone call.
Signaling for packet switching networks were first developed to provide grades of service better than the default xe2x80x9cbest-effortxe2x80x9d, most notably for interactive packet voice and video applications. Two signaling protocols that were developed for IP networks, e.g., the Internet, are ST-II [C. Topolcic (Ed.) Experimental Internet Stream Protocol, Version 2 (ST-II), RFC 1190, October 1990] and RSVP [R. Braden, Resource ReSerVation Protocol (RSVP)xe2x80x94Version 1 Functional Specification., IETF Request for Comment RFC2205, September 1997]. Messages of these protocols, which are carried in band between neighboring packet switches, convey requests for allocation of link capacity and buffer space. UNI3.1, is a signaling protocol for ATM networks, which is also in band control [R. Handel, M. N. Huber, and S. Schroder. ATM Networks: Concepts, Protocols, and Applications (2nd Ed.). Addison-Wesley, 1994]. The signaling protocols for packet switching networks are as effective as the underlying mechanisms for reserving resources.
This invention describes a method for controlling the creation of data paths of predefined capacity that is needed for timely forwarding of packets in networks where the switches maintain a common time reference. The invention describes a signaling controller that is responsive to a setup request by computing a route of switches for data transmission, and a transmission schedule, which consists of predetermined time frames in which the switches along the route may forward packets of said setup request. The invention describes a switch signaling controller, which operates in every switch and which sends and is responsive to messages regarding reserving and releasing bandwidth on the switch""s ports. The invention describes a protocol by which end-stations, signaling controller, and switch signaling controllers communicate to establish paths of specified capacities; and algorithms for processing signaling messages and finding transmission schedule in the network.
This invention teaches a method for signaling in packet switching networks that differ from the aforementioned protocols in the following: (1) it is designed for a network where the switches have a common time frame, using which precise resource allocation and data delivery parameters can be configured, and (2) its signaling messages are carried out of band, that is, through a data networkxe2x80x94e.g., the Internet or ATM-which is separate from the network on which data packets are transmitted.
The method and apparatus that are disclosed in this invention aim at providing virtual pipes that carry real-time traffic over packet switching networks while guaranteeing end-to-end performance. The method combines the advantages of both circuit and packet switching. It provides for allocation for the exclusive use of predefined connections and for those connections it guarantees loss free transport with low delay and jitter. When predefined connections do not use their allocated resources, other packets can use them without affecting the performance of the predefined connections.
Under the aforementioned prior art methods for providing packet switching services, switches and routers operate asynchronously. This invention describes a method that controls and manages the provisioning of real-time services by synchronous methods that utilize a time reference that is common to the switches and end-stations comprising a wide area network. The common time reference can be realized by using UTC (Coordinated Universal Time), which is globally available via, for example, GPS (Global Positioning System) [T. Piotrowski. Synchronization of telecommunication network using a global positioning satellite. IEEE PLANS""92, March 1992]xe2x80x94see for example: http://www.utexas.edu/depts/grg/gcraft/notes/gps/gps.html). By international agreement, UTC is the same all over the world. UTC is the scientific name for what is commonly called GMT (Greenwich Mean Time), the time at the 0 (root) line of longitude at Greenwich, England. In 1967, an international agreement established the length of a second as the duration of 9,192,631,770 oscillations of the cesium atom. The adoption of the atomic second led to the coordination of clocks around the world and the establishment of UTC in 1972. The Time and Frequency Division of the National Institute of Standard and Technologies (NIST) (see http:  www.boulder.nist.gov/timefreq) is responsible for coordinating with the International Bureau of Weights and Measures (BIPM) in Paris in maintaining UTC.
UTC timing is readily available to individual PCs through GPS cards. For example, TrueTime, Inc.""s PCI-SG provides precise time, with zero latency, to computers that have PCI extension slots. Another way by which UTC can be provided over a network is by using the Network Time Protocol (NTP) [D. Mills, Network time protocol (Version 3), IETF RFC1305], however, the clock accuracy is not adequate for inter-switch coordination, on which this invention is based.
Two internet-based signaling protocols are based on out-of-band message exchange for marshaling resources. The Session Invitation Protocol (SIP) is designed to carry to potential session participants information about the session that they are invited to join including the types of data that are exchanged in the session and the quality of service needed to participate [M. Handley et. al, SIP-Session Initiation Protocol  less than draft-draft-ietf-mmusic-sip-04.ps greater than  November 1997]. SIP, however, does not results in allocation of resources. The Common Open Policy Service Protocol (COPS) is conducted between a QoS policy server and network switches/routers. COPS, however, is not capable of dealing with networks that maintain a common time frame and it cannot guarantee performance to end users [J. Boyle et al., The COPS (Common Open Policy Service) Protocol. Internet Draft.  less than draft-ietf-rap-cops-01.txt greater than . March 1998].
U.S. Pat. No. 5,623,483 [P. Agrawal et al. xe2x80x9cSynchronization system for networked multimedia streamsxe2x80x9d, U.S. Pat. No. 5,623,483 Issued Apr. 22, 1997] discloses a method for network data stream synchronization method, which accepts loss parameters and initialized a data stream buffer. The method measures actual network delay experienced by a data packet and imposes a buffer delay to provide a fixed end-to-end delay. Packets arriving too late to be played within the fixed end-to-end delay are discarded. This methods, however, only attempts to adapt to delay under asynchronous data transfer and does not guarantee a predetermined delay. Another related method is disclosed in U.S. Pat. No. 4,821,259 [D. DeBruler et al., xe2x80x9cControl information communication arrangement for a distributed control switching systemxe2x80x9d, U.S. Pat. No. 4,821,259, Issued Apr. 11, 1989].
U.S. Pat. No. 5,442,636 [M. H. Bontekoe, xe2x80x9cCircuit and method for alignment of digital information packetsxe2x80x9d, U.S. Pat. No. 5,442,636 Issued Aug. 15, 1995] discloses a method that is aims at enforcing uniform inter-packet delay in an asynchronous packet switching network. The method describes a frame aligner circuit for aligning a plurality of information packet signals received within a maximum starting time variation interval consists of a plurality of frame detectors, stretch circuits and variable delay circuits which are controlled by a synchronization signal generator and a delay control circuit. This methods however, does not deal with switches that maintain a common time reference and cannot recover from temporary gradual increase in network delay. Also, this patent does not provide a method for signaling to establish a path of desired characteristics.
The international organization for telecommunication standards, ITU-T, completed in recent years a comprehensive set of documents for implementing multimedia (i.e., voice, video and data) and teleconferencing over the Internet. This standard is called H.323, which include among many other documents the following two: [ITU-T Visual telephone systems and equipment for local area networks which provide a non-guaranteed quality of service, ITU-T Recommendation H.323, 1996] and [ITU-T Line transmission of non-telephone signals: Control protocol for multimedia communication. ITU-T Recommendation H.245, 1994]. The H.323 has adapted the Internet""s real-time protocol (RTP), see the following reference for more details: [H. Schultzinne et. al, RTP: A Transport Protocol for Real-Time Applications, IETF Request for Comment RFC1889, January 1996].
These and other aspects and attributes of the present invention will be discussed with reference to the following drawings and accompanying specification.